package varvelworld.algorithm.DuplicationFinding;

import java.util.ArrayList;
import java.util.List;

public class WeakHash implements IDuplicationFinding {

    @Override
    public List<Long> execute(long[] a) {
        List<Long> result = new ArrayList<Long>();
        Node[] c = new Node[(int) (a.length / 0.75)];
        System.out.println("hash table length is " + c.length);
        int conflict = 0;
        int maxDeep = 0;
        for(int i = 0; i < a.length; i++){
            int k = Math.abs((int)(a[i] ^ (a[i] >>> 32)) % c.length);
            if(c[k] == null){
                c[k] = new Node(a[i], 1);
                continue;
            }
            conflict++;
            Node n = c[k];
            int deep = 0;
            while(true){
            	deep++;
                if(n.v == a[i]){
                    n.s++;
                    if(n.s == 2){
                        result.add(n.v);
                    }
                    break;
                }
                else if(n.next == null){
                    n.next = new Node(a[i], 1);
                    break;
                }
                else{
                    n = n.next;
                }
            }
            if(deep > maxDeep){
            	maxDeep = deep;
            }
        }
        System.out.println("conflict is " + conflict);
        System.out.println("maxDeep is " + maxDeep);
        return result;
    }
    
    static class Node{
        long v;
        int s;
        Node next;
        public Node(long v, int s){
            super();
            this.v = v;
            this.s = s;
        }
        
    }

}
